package com.linyaonan.leetcode.hard._52;

/**
 *
 * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给定一个整数 n，返回 n 皇后不同的解决方案的数量。
 *
 * @author: Lin
 * @date: 2020/1/18
 */
public class QueensII {
    int sum = 0;
    public int totalNQueens(int n) {
        // 1.定义棋盘
        int[][] queue = new int[n][n];
        // 2.回溯
        backTracing(queue, 0, n);
        return sum;
    }

    private void backTracing(int[][] queue, int row, int n) {
        if (row == n) {
            sum++;
            return;
        }
        //
        for (int i = 0; i < queue[0].length; i++) {
            if (isVaild(queue, row, i)) {
                queue[row][i] = 1;
                // 递归
                backTracing(queue, row + 1, n);
                // 回溯
                queue[row][i] = 0;
            }
        }
    }

    private boolean isVaild(int[][] queue, int x, int y) {
        for (int i = 0; i <= x; i++) {
            for (int j = 0; j < queue[0].length; j++) {
                // y的上方，x到i的距离与y到j的距离一致
                if (queue[i][j] == 1 && (j == y || Math.abs(x - i) == Math.abs(y - j))) {
                    return false;
                }
            }
        }
        return true;
    }

}
